//爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下： 
//
// 爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 
//maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。 
//
// 当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。 
//
// 爱丽丝的分数不超过 n 的概率是多少？ 
//
// 与实际答案误差不超过 10⁻⁵ 的答案将被视为正确答案。 
//
// 示例 1： 
//
// 
//输入：n = 10, k = 1, maxPts = 10
//输出：1.00000
//解释：爱丽丝得到一张牌，然后停止。
// 
//
// 示例 2： 
//
// 
//输入：n = 6, k = 1, maxPts = 10
//输出：0.60000
//解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
// 
//
// 示例 3： 
//
// 
//输入：n = 21, k = 17, maxPts = 10
//输出：0.73278
// 
//
// 
//
// 提示： 
//
// 
// 0 <= k <= n <= 10⁴ 
// 1 <= maxPts <= 10⁴ 
// 
//
// Related Topics 数学 动态规划 滑动窗口 概率与统计 👍 442 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-08-18 23:32:02
 * @description 837.新 21 点
 */
public class New21Game{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 New21Game fun=new New21Game();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //>=k，可能是多种情况
	// 设计一个数组 dp，其中 dp[i] 表示当前得分为 i 时，最终停止不超过n的概率。
	//求 dp[0]的概率，
	/*
如果 x ≥ k：停止抽牌。
如果 x ≤ n，则 dp[x] = 1（成功）。
如果 x > n，则 dp[x] = 0（失败）。
如果 x < k：需要抽一张牌 y（y 在 [1, maxPts] 均匀随机）。
抽 y 后，新分数为 x + y，对应的概率为 dp[x + y]。
因此，dp[x] = (dp[x + 1] + dp[x + 2] + ... + dp[x + maxPts]) / maxPts。
边界条件：
对于 x ≥ k：
dp[x] = 1 if x ≤ n，
dp[x] = 0 if x > n。
计算顺序：
从高到低计算 dp[x]，因为 dp[x] 依赖于更高的 x 值。
具体来说，可以从 x = k + maxPts 开始（因为 x ≥ k + maxPts 时，x > n 的可能性大），
向下计算到 x = 0。


具体步骤
初始化：
创建 dp 数组，大小为 k + maxPts（因为 x 最大可能到 k + maxPts - 1）。
对于 x ≥ k：
	dp[x] = 1 if x ≤ n，
	dp[x] = 0 otherwise。
滑动窗口和：
	初始化 window_sum 为 dp[k] + dp[k + 1] + ... + dp[k + maxPts - 1]。
	对于 x 从 k - 1 到 0：
	dp[x] = window_sum / maxPts。
	更新 window_sum：
	window_sum += dp[x] - dp[x + maxPts]。
结果：
dp[0] 即为所求概率。
边界情况
如果 k == 0：爱丽丝一开始就停止，分数为0 ≤ n，概率为1。
如果 n >= k + maxPts：因为每次最多加 maxPts，所以停止时分数最多为 k + maxPts - 1。如果 n >= k + maxPts - 1，概率为1。
如果 maxPts == 0：但题目中 maxPts >= 1。
	* */
    public double new21Game(int n, int k, int maxPts) {
        if(k==0) return 1.0;
		// >=k停止，那么最大就是k + maxPts - 1
		double dp[] = new double[k + maxPts];
		for (int i = k; i < Math.min(n+1,k+maxPts); i++) {
			dp[i] = 1.0; // 如果 i >= k 且 i <= n，则概率为 1
		}
		double window_sum = 0.0;
		// 每次计算概率都需要从1~k相加然后除以 maxPts，可以直接初始化滑动窗口
		// 每次从 k 开始向下遍历，计算 dp[i] 的概率
		for (int i = k; i < k + maxPts; i++) {
				window_sum += dp[i]; // 初始化窗口和
		}
		//从 x = k - 1 开始向下遍历：
		for (int i = k - 1; i >= 0; i--) {
			dp[i] = window_sum / maxPts; // 计算 dp[i]
			if (i + maxPts < dp.length) {
				//更新 windowSum：加上当前的 dp[x]，减去 dp[x + maxPts]（滑动窗口的右边界）。
				window_sum += dp[i] - dp[i + maxPts]; // 更新窗口和
			}
		}
		return dp[0]; // 返回 dp[0] 即为所求概率
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
